个人中有 个罪犯,每个人说一句话,说第 个人是/不是罪犯,其中有 句真话,要判断这些话的真假。
思路:
首先假设所有人都不是罪犯,统计出真话条数,然后枚举每一个人,在这个真话条数的基础上加上这个人是罪犯时对答案的贡献,如果刚好有 句真话,标记有嫌疑,最后判断即可。
但是这个贡献怎么求呢?
很简单,如果所有人都不是罪犯,则真话条数就是 的数量;当 是罪犯时,减去 的数量,加上 的数量,即为最新的贡献,这里在读入时也处理出来。
最后话的真假的判断方式也很简单:
如果 指控一个人是罪犯:经过如上处理,发现他不可能是罪犯,则为假话;如果他可能是罪犯且嫌疑人数为 ,则为真话;否则不确定。说一个人不是罪犯的情况类似,不展开细说,可以参考代码。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define fil(x,y) memset(x, y, sizeof(x))
#define mulT0 int T; for(scanf("%d", &T);T;T--)
#define mulT1 int T, rnds; for(scanf("%d", &T),rnds=1;rnds<=T;rnds++)
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int n, m, a[N], contribution[N], suspect[N], tot, s;
int main() {
scanf("%d%d", &n, &m);
rep(i, 1, n) {
scanf("%d", &a[i]);
if(a[i] > 0) ++contribution[a[i]];
else --contribution[-a[i]], ++s;
}
rep(i, 1, n) if(s + contribution[i] == m) suspect[i] = 1, ++tot;
rep(i, 1, n) {
if(a[i] > 0) {
if(!suspect[a[i]]) puts("Lie");
else if(tot == 1) puts("Truth");
else puts("Not defined");
}
else {
if(!suspect[-a[i]]) puts("Truth");
else if(tot == 1) puts("Lie");
else puts("Not defined");
}
}
return 0;
}